package com.liudachu.interview.bishi;

import java.util.ArrayList;
import java.util.Stack;

/**
 * 栈相关笔试
 */
public class StackTest {
    /**
     * 栈排序
     * @param a int整型一维数组 描述入栈顺序
     * @return int整型一维数组
     */
    public int[] solve (int[] a) {
        // write code here
        Stack<Integer> stack = new Stack<>();

        for (int i : a) {
            stack.push(i);
        }

        //额外的出栈
        Stack<Integer> resultstack = new Stack<>();

        while (!stack.isEmpty()){
            if (resultstack.empty()){
                resultstack.push(stack.pop());
            }else {
                int b=stack.pop();
                int c=resultstack.pop();
                if (b<c){
                    stack.push(b);
                    while (!resultstack.empty() && b<(c=resultstack.pop())){
                        stack.push(c);
                    }
                }
                if (b>=c){
                    resultstack.push(c);
                }
                resultstack.push(b);
            }
        }

        ArrayList<Integer> result = new ArrayList<Integer>();

        while (!resultstack.empty()){
            result.add(resultstack.pop());
        }

        int[] arr=new int[result.size()];
        int i=0;
        for (Integer integer : result) {
            arr[i]=integer;
        }
        return arr;

    }







    public int findtheNumber (int[] arr, int k) {
        // write code here
        int result=4;
        for (int i = 0; i < arr.length; i++) {
            int a=arr[i];
            int count=0;
            for (int i1 : arr) {
                if (arr[i1]==a){
                    count++;
                }
            }
            if (count==1){
                result=a;
            }
        }
        return result;
    }



    public int[] LIS (int[] arr) {
        // write code here
        int[] dp = new int[arr.length];


        for (int i = 0; i < arr.length; i++) {
            dp[i]=1;
        }

        int max=1;
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < i; j++) {
                if (arr[j]<arr[i] && (arr[j]+1)>arr[i]){
                    dp[i]=dp[j]+1;
                }
                if (max<dp[i]){
                    max=dp[i];
                }
            }
        }

        return new int[]{1,3,4,8,9};
    }

}
